//二叉树的序列化与反序列化
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

// Definition for a binary tree node.
  struct TreeNode {
     int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };
 
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(root==NULL){
            return "null_";
        }
        //先序遍历实现转化为字符串
        string tempLeft = serialize(root->left);
        string tempRight = serialize(root->right);
        return to_string(root->val)+'_'+tempLeft+tempRight;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        //先对string进行处理
        vector<string> datavalue;
        string temp = "";
        for(int i = 0;i<data.size();++i){
            if(data[i]!='_'){
                temp += data[i];
            }
            else{
                datavalue.push_back(temp);
                temp = "";
            }
        }
        //对daatavalue进行建树
        int i = 0;
        return func(datavalue,i);

        
    }

    TreeNode* func(vector<string>& datavalue,int& i){
        if(datavalue[i]=="null"){
            return NULL;
        }
        TreeNode* head = new TreeNode(stoi(datavalue[i]));
        
        head->left = func(datavalue,++i);
        head->right = func(datavalue,++i);
        return head;

    }

    
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));


int main(){
    TreeNode* head = new TreeNode(1);
    head->left = new TreeNode(2);
    head->right = new TreeNode(3);
    head->right->left = new TreeNode(4);
    head->right->right = new TreeNode(5);
    Codec S;
    string temp = S.serialize(head);
    cout<<temp<<endl;
    TreeNode* root = S.deserialize(temp);
    return 0;
    
    
}